package net.cyndeline.rlgraph.planar.face

import scalax.collection.mutable.Graph
import scalax.collection.GraphEdge._
import scalax.collection.GraphPredef._
import net.cyndeline.rlgraph.planar.ComputeFaceOperation
import net.cyndeline.rlgraph.embedding.{AdjacencyList, PlanarEmbedding}
import scala.collection.mutable.ArrayBuffer
import scala.reflect.runtime.universe._
import scala.reflect.ClassTag

class FaceComputation[VType : TypeTag : ClassTag] extends ComputeFaceOperation[VType] {
  /**
   * Creates a directed graph for each edge in an embedding, with two directed edges going both ways
   * between every pair of vertices. The algorithm then selects one edge at random, and traverses the embedding
   * in a counter clockwise direction until it reaches the original edge. Every edge traversed this way
   * is part of a face.
   *
   * @param embedding A planar embedding of a graph connected graph, where edges are embedded in a clockwise
   *                  order around each vertex.
   * @return A list of faces, where each face is represented by a list of vertices in the order they are
   *         traversed around the face. The last entry in the face is implied to be connected to the first.
   */
  def computeFaces(embedding: PlanarEmbedding[VType]): List[Face[VType]] = {
    val graph = Graph[VType, DiEdge]()
    val embeddedValues: Iterator[(VType, AdjacencyList[VType])] = embedding.iterator

    /*
     * STEP 1: Setup a graph representation of the embedding, with two directed edges for each edge
     * in the embedding. Duplicates will be filtered out by the insertion.
     */
    while (embeddedValues.hasNext) {
      val vertexAdjacencyList: (VType, AdjacencyList[VType]) = embeddedValues.next
      val vertex = vertexAdjacencyList._1
      val adjacencyList = vertexAdjacencyList._2
      val entries = adjacencyList.iterator

      while(entries.hasNext) {
        val entry = entries.next()
        graph += (vertex~>entry.vertex)
        graph += (entry.vertex~>vertex)
      }
    }

    /*
     * STEP 2: Traverse and delete edges until the graph is empty. Traversal order is selected using the embedding.
     */
    val faces = new ArrayBuffer[Face[VType]]
    while (graph.edges.size > 0) {
      val randomEdge: DiEdge[VType] = graph.edges.toOuter.toSet[DiEdge[VType]].head
      val to = randomEdge.to
      val from = randomEdge.from
      val face = new ArrayBuffer[VType]()

      /* The traversal starts at the edge incident to the random edge, to keep the start-point in the graph. */
      var faceEdge = nextEdge(from, to, embedding, graph)

      while(faceEdge != randomEdge) {
        val fTo = faceEdge.to
        val fFrom = faceEdge.from
        face += fFrom
        graph -= faceEdge
        faceEdge = nextEdge(fFrom, fTo, embedding, graph)
      }

      graph -= randomEdge
      face += from
      faces += new Face(face.toList)
      face.clear()
    }

    faces.toList
  }

  private def nextEdge(from: VType, to: VType, embedding: PlanarEmbedding[VType], graph: Graph[VType, DiEdge]): DiEdge[VType] = {
    val toEmbedding = embedding.embeddingFor(to)
    val fromEntry = toEmbedding.get.entryFor(from)

    var current = fromEntry.previous
    do {
      val edge = to~>current.vertex
      if (graph.contains(edge)) {
        return edge
      } else {
        current = current.previous
      }

    } while (current.vertex != fromEntry.vertex)

    throw new IllegalArgumentException("The graph " + graph + " contained no edge going from " + to + " to another edge in the embedding " + toEmbedding)
  }
}
